package tianhao.luo.algorithm;

/**
 * 基数排序
 *
 * @author: tianhao.luo@hand-china.com 2021/6/18  21:41
 */
public class RadixSort {

    private int[] array;

    public RadixSort(int[] array) {
        this.array = array;
    }

    /**
     * 基数排序
     */
    public void sort(){

        /*推导过程
        // 第一轮(针对每一个元素的个位数进行排序处理)

        // 定义一个二维数组,表示10个桶,每个桶就是一个一维数组
        // 说明
        // 1.二维数组包含10个一维数组
        // 2.为了防止在放入数的时候,数据溢出,则每一个一位数组,大小定为arr.length
        // 3.明确,基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][array.length];

        // 为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入数据的个数

        int[] bucketElementCounts = new int[10];

        // 第一轮(针对每个元素的个位进行排序处理)
        for (int i = 0; i < array.length; i++) {
            // 取出每个元素的个位的值
            int digitOfElement = array[i]%10;
            // 放入到对应桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = array[i];
            // 记录装入元素的个数
            bucketElementCounts[digitOfElement]++;
        }

        // 原数组的临时索引
        int index =0;
        // 按照桶的顺序取出数据
        // 遍历每一个桶,并将桶中的数据,放入原数组
        for (int i = 0; i < bucketElementCounts.length; i++) {
            // 如果桶中有数据,我们才去取出数据
            if (bucketElementCounts[i] >0){
                // 循环该桶内部的元素,放入
                for (int j = 0; j < bucketElementCounts.length; j++) {
                    // 取出元素放入原数组
                    array[index] = bucket[i][j];
                    index++;
                }
            }
            // 每一轮处理后,需要将bucketElementCounts[i] =0
            bucketElementCounts[i] =0;
        }


        //==================================================

        // 第二轮(针对每个元素的十位进行排序处理)
        for (int i = 0; i < array.length; i++) {
            // 取出每个元素的个位的值
            int digitOfElement = array[i] /10 %10;
            // 放入到对应桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = array[i];
            // 记录装入元素的个数
            bucketElementCounts[digitOfElement]++;
        }

        // 原数组的临时索引
        index =0;
        // 按照桶的顺序取出数据
        // 遍历每一个桶,并将桶中的数据,放入原数组
        for (int i = 0; i < bucketElementCounts.length; i++) {
            // 如果桶中有数据,我们才去取出数据
            if (bucketElementCounts[i] >0){
                // 循环该桶内部的元素,放入
                for (int j = 0; j < bucketElementCounts.length; j++) {
                    // 取出元素放入原数组
                    array[index] = bucket[i][j];
                    index++;
                }
            }
            // 每一轮处理后,需要将bucketElementCounts[i] =0
            bucketElementCounts[i] =0;
        }

        //==================================================

        // 第三轮(针对每个元素的十位进行排序处理)
        for (int i = 0; i < array.length; i++) {
            // 取出每个元素的个位的值
            int digitOfElement = array[i] /100 %10;
            // 放入到对应桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = array[i];
            // 记录装入元素的个数
            bucketElementCounts[digitOfElement]++;
        }

        // 原数组的临时索引
        index =0;
        // 按照桶的顺序取出数据
        // 遍历每一个桶,并将桶中的数据,放入原数组
        for (int i = 0; i < bucketElementCounts.length; i++) {
            // 如果桶中有数据,我们才去取出数据
            if (bucketElementCounts[i] >0){
                // 循环该桶内部的元素,放入
                for (int j = 0; j < bucketElementCounts.length; j++) {
                    // 取出元素放入原数组
                    array[index] = bucket[i][j];
                    index++;
                }
            }
            // 每一轮处理后,需要将bucketElementCounts[i] =0
            bucketElementCounts[i] =0;
        }
         */
        // 1.得到数组中最大的数的位数
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i]>max){
                max = array[i];
            }
        }
        // 2.得到最大的数为几位数
        int maxLength = (max+"").length();

        // 定义一个二维数组,表示10个桶,每个桶就是一个一维数组
        // 说明
        // 1.二维数组包含10个一维数组
        // 2.为了防止在放入数的时候,数据溢出,则每一个一位数组,大小定为arr.length
        // 3.明确,基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][array.length];

        // 为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入数据的个数

        int[] bucketElementCounts = new int[10];
        for (int n = 0,k=1; n <= maxLength; n++,k=k*10) {
            for (int i = 0; i < array.length; i++) {
                // 取出每个元素的个位的值,注意需要取绝对值,不然计算出来的digitOfElement是负数
                int digitOfElement = Math.abs(array[i]) /k %10;
                // 放入到对应桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = array[i];
                // 记录装入元素的个数
                bucketElementCounts[digitOfElement]++;
            }

            // 原数组的临时索引
            int index =0;
            // 按照桶的顺序取出数据
            // 遍历每一个桶,并将桶中的数据,放入原数组
            for (int i = 0; i < bucketElementCounts.length; i++) {
                // 如果桶中有数据,我们才去取出数据
                if (bucketElementCounts[i] >0){
                    // 循环该桶内部的元素,放入
                    for (int j = 0; j < bucketElementCounts[i]; j++) {
                        // 取出元素放入原数组
                        array[index] = bucket[i][j];
                        index++;
                    }
                }
                // 每一轮处理后,需要将bucketElementCounts[i] =0
                bucketElementCounts[i] =0;
            }
        }
    }

    /**
     * 打印
     */
    public void print(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
    }
}
